package com.zzg.datastructure.tree.entity;

import lombok.*;

import java.util.Objects;

/**
 * @Author zhengzg
 * @Date 2022-09-16
 * @Version v1.0
 */
@Getter
@Setter
@ToString(exclude = {"left","right","leftType","rightType"})
public class HeroNode {
    private int no;

    private String name;

    /**
     * 左节点
     */
    private HeroNode left;

    /**
     * 右节点
     */
    private HeroNode right;

    /**
     * 如果leftType == 0 表示指向是左子树，如果1则表示指向前驱节点
     */
    private int leftType;

    /**
     * 如果rightType == 0表示指向的是右子树，如果1则表示指向后续节点
     */
    private int rightType;

    public HeroNode(int no, String name) {
        this.no = no;
        this.name = name;
    }

    /**
     * 前序遍历
     */
    public void perOrder(){
        // 先输出父节点
        System.out.println(this);

        // 递归向左遍历
        if (Objects.nonNull(this.left)) {
            this.left.perOrder();
        }

        // 递归向右遍历
        if (Objects.nonNull(this.right)) {
            this.right.perOrder();
        }
    }

    /**
     * 中序遍历
     */
    public void infixOrder() {
        // 递归向左遍历
        if (Objects.nonNull(this.left)) {
            this.left.infixOrder();
        }
        System.out.println(this);
        // 递归向右遍历
        if (Objects.nonNull(this.right)) {
            this.right.infixOrder();
        }
    }

    /**
     * 后续遍历
     */
    public void postOrder() {
        // 递归向左遍历
        if (Objects.nonNull(this.left)) {
            this.left.postOrder();
        }

        // 递归向右遍历
        if (Objects.nonNull(this.right)) {
            this.right.postOrder();
        }

        System.out.println(this);
    }

    /**
     * 前序查找
     * @param no 要查找的编号
     * @return 返回Node或者null
     */
    public HeroNode perOrderSearch(int no) {
        System.out.println("进入前序遍历");
        // 比较当前节点是不是
        if (Objects.equals(this.no, no)) {
            return this;
        }

        // 判断当前节点的左子节点是否是null，如果不是null，则递归前序查找
        HeroNode resNode = null;
        if (Objects.nonNull(this.left)) {
            resNode = this.left.perOrderSearch(no);
        }

        // 此时在左子树找到节点
        if (Objects.nonNull(resNode)) {
            return resNode;
        }

        // 判断左子树完成，开始判断右子树
        if (Objects.nonNull(this.right)) {
            resNode = this.right.perOrderSearch(no);
        }

        return resNode;
    }

    /**
     * 中序遍历查找
     * @param no
     * @return
     */
    public HeroNode infixOrderSearch(int no) {
        HeroNode resNode = null;
        // 判断当前节点的左子节点是否为null
        if (Objects.nonNull(this.left)) {
            resNode = this.left.infixOrderSearch(no);
        }
        // 在左子树找到节点
        if (Objects.nonNull(resNode)) {
            return resNode;
        }
        System.out.println("进入中序查找");
        // 如果找到则返回，没有找到，就和当前节点比较如果是则返回当前节点
        if (this.no == no) {
            return this;
        }
        // 继续向右递归寻找
        if (Objects.nonNull(this.right)) {
            resNode = this.right.infixOrderSearch(no);
        }
        return resNode;
    }

    /**
     * 后续遍历查找
     * @param no
     * @return
     */
    public HeroNode postOrderSearch(int no) {
        HeroNode resNode = null;
        // 判断当前节点的左子节点是否为null
        if (Objects.nonNull(this.left)) {
            resNode = this.left.infixOrderSearch(no);
        }
        // 在左子树找到节点
        if (Objects.nonNull(resNode)) {
            return resNode;
        }
        // 继续向右递归寻找
        if (Objects.nonNull(this.right)) {
            resNode = this.right.infixOrderSearch(no);
        }
        if (Objects.nonNull(resNode)) {
            return resNode;
        }
        System.out.println("进入后序查找");
        // 如果找到则返回，没有找到，就和当前节点比较如果是则返回当前节点
        if (this.no == no) {
            return this;
        }
        return resNode;
    }


    public void delNode(int no) {
        // 如果当前节点的左子节点不为null，并且左子节点就是要删除的节点
        if (Objects.nonNull(this.left) && Objects.equals(no,this.left.no)) {
            // 判断节点是否是叶子节点
            boolean left = Objects.nonNull(this.left.left);
            boolean right = Objects.nonNull(this.left.right);
            if (left || right) {
                if (!right) {
                    // 表明只存在一个左节点
                    this.left = this.left.left;
                }
                if (!left) {
                    // 表明只存在一个右节点
                    this.left = this.left.right;
                }
                if (left && right) {
                    this.left = this.left.left;
                }
                return;
            }
            this.left = null;
            return;
        }

        // 如果当前节点的右子节点不是null，并且右子节点就是要删除的节点
        if (Objects.nonNull(this.right) && Objects.equals(no,this.right.no)) {
            // 判断节点是否是叶子节点
            boolean left = Objects.nonNull(this.right.left);
            boolean right = Objects.nonNull(this.right.right);
            if (left || right) {
                if (!right) {
                    // 表明只存在一个左节点
                    this.right = this.right.left;
                }
                if (!left) {
                    // 表明只存在一个右节点
                    this.right = this.right.right;
                }
                if (left && right) {
                    // 表明只存在一个左节点
                    this.right = this.right.left;
                }
                return;
            }
            this.right = null;
            return;
        }

        // 上面两种情况都不满足，先向左遍历，然后向右遍历
        if (Objects.nonNull(this.left)) {
            this.left.delNode(no);
        }

        if (Objects.nonNull(this.right)) {
            this.right.delNode(no);
        }
    }

    /**
     * 递归删除节点
     *
     * @param no   节点ID
     * @param flag 与重载方法区分
     */
    public void delNode(int no,boolean flag) {
        /*
         * 1. 因为我们的二叉树是单向的，所以我们是判断当前结点的子结点是否需要删除结点，而不能去判断 当前这个结点是不是需要删除结点.
         * 2. 如果当前结点的左子结点不为空，并且左子结点 就是要删除结点，就将 this.left = null; 并且就返回 (结束递归删除)
         * 3. 如果当前结点的右子结点不为空，并且右子结点 就是要删除结点，就将 this.right= null ;并且就返回 (结束递归删除)
         * 4. 如果第 2 和第 3 步没有删除结点，那么我们就需要向左子树进行递归删除
         * 5. 如果第 4 步也没有删除结点，则应当向右子树进行递归删除.
         */
        if (Objects.nonNull(this.left) && this.left.no == no) {
            this.left = null;
            return;
        }

        if (Objects.nonNull(this.right) && this.right.no == no) {
            this.right = null;
            return;
        }

        if (Objects.nonNull(this.left)) {
            this.left.delNode(no);
        }

        if (Objects.nonNull(this.right)) {
            this.right.delNode(no);
        }
    }










}
